Descriptoin

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

Answer & Explaining

#include <stdio.h>

int rob(int* nums, int numsSize) {
    // 如果只有一間房屋，直接返回該房屋的金額
    if (numsSize == 1) {
        return nums[0];
    }
    // 如果有兩間房屋，選擇金額較大的那間偷
    if (numsSize == 2) {
        return nums[0] > nums[1] ? nums[0] : nums[1];
    }
    
    // 初始化變數
    // prev1 表示偷到前兩間房屋的最大金額
    int prev1 = nums[0];
    // prev2 表示偷到前兩間或前一間房屋的最大金額
    int prev2 = nums[0] > nums[1] ? nums[0] : nums[1];
    // maxMoney 用來儲存當前房屋可以偷到的最大金額
    int maxMoney = prev2;
    
    // 從第三間房屋開始，依序計算最大金額
    for (int i = 2; i < numsSize; i++) {
        // maxMoney 是在不偷相鄰房屋的情況下可以偷到的最大金額
        // 有兩種選擇：
        // 1. 不偷當前這間房屋，那最大金額就是 prev2
        // 2. 偷當前這間房屋，那最大金額就是 prev1 + nums[i]
        // 選擇其中較大的值
        maxMoney = (prev1 + nums[i] > prev2) ? prev1 + nums[i] : prev2;
        
        // 更新 prev1 和 prev2，為下一輪迭代做準備
        prev1 = prev2;
        prev2 = maxMoney;
    }
    
    // 最終結果是 maxMoney，表示可以偷到的最大金額
    return maxMoney;
}

Testing

#include <stdio.h>

int rob(int* nums, int numsSize) {
    // 如果只有一間房屋，直接返回該房屋的金額
    if (numsSize == 1) {
        return nums[0];
    }
    // 如果有兩間房屋，選擇金額較大的那間偷
    if (numsSize == 2) {
        return nums[0] > nums[1] ? nums[0] : nums[1];
    }
    
    // 初始化變數
    // prev1 表示偷到前兩間房屋的最大金額
    int prev1 = nums[0];
    // prev2 表示偷到前兩間或前一間房屋的最大金額
    int prev2 = nums[0] > nums[1] ? nums[0] : nums[1];
    // maxMoney 用來儲存當前房屋可以偷到的最大金額
    int maxMoney = prev2;
    
    // 從第三間房屋開始，依序計算最大金額
    for (int i = 2; i < numsSize; i++) {
        // maxMoney 是在不偷相鄰房屋的情況下可以偷到的最大金額
        // 有兩種選擇：
        // 1. 不偷當前這間房屋，那最大金額就是 prev2
        // 2. 偷當前這間房屋，那最大金額就是 prev1 + nums[i]
        // 選擇其中較大的值
        maxMoney = (prev1 + nums[i] > prev2) ? prev1 + nums[i] : prev2;
        
        // 更新 prev1 和 prev2，為下一輪迭代做準備
        prev1 = prev2;
        prev2 = maxMoney;
    }
    
    // 最終結果是 maxMoney，表示可以偷到的最大金額
    return maxMoney;
}

// 測試函數
void test() {
    int test1[] = {1, 2, 3, 1};
    int test2[] = {2, 7, 9, 3, 1};
    int test3[] = {2, 1, 1, 2};
    int test4[] = {10};
    int test5[] = {5, 5, 10, 100, 10, 5};
    
    printf("Test 1: %d\n", rob(test1, sizeof(test1) / sizeof(test1[0]))); // 預期輸出: 4
    printf("Test 2: %d\n", rob(test2, sizeof(test2) / sizeof(test2[0]))); // 預期輸出: 12
    printf("Test 3: %d\n", rob(test3, sizeof(test3) / sizeof(test3[0]))); // 預期輸出: 4
    printf("Test 4: %d\n", rob(test4, sizeof(test4) / sizeof(test4[0]))); // 預期輸出: 10
    printf("Test 5: %d\n", rob(test5, sizeof(test5) / sizeof(test5[0]))); // 預期輸出: 110
}

int main() {
    test();
    return 0;
}